package leetCode.sample;

import org.junit.Test;

import java.util.*;

/**
 * @author: zhangzhiping
 * @date: 2019/12/1 14:52
 * @description: 三数之和
 */
public class ThreeSumSolution {

    @Test
    public void test() {
        int x = 1;
        System.out.println(x++);
        System.out.println(++x);
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum(new int[]{-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6}));

        System.out.println(threeSum2(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum2(new int[]{-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6}));

    }


    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        //排序
        Arrays.sort(nums);
        //用一个HashMap将所有的元素加进去，这里的keys是nums[i]，value是i
        //如果出现重复的key,那么新出现的value将会覆盖前面的一个value，我们用这个map来替代第三重循环
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length - 2; i++) {
            int x = nums[i];
            //去重，假如给的用例是[0, 0, 0, 0],当i第一次遇到0时，为首次遇见没有关系，可如果这次i的循环结束了
            //i+1进入第二次循环，那么这时候还是遇到0，为连续的第二次遇见，这就造成了前后重复，必须要跳过
            if (x > 0) break;
            if (i > 0 && nums[i - 1] == nums[i]) continue;
            for (int j = i + 1; j < nums.length - 1; j++) {
                int y = nums[j];
                if (x + y > 0) break;
                //去重原理同i，j必须大于i + 1，因为j是从i + 1开始的，必须要大于开始值才能后退一步
                if (j > i + 1 && nums[j - 1] == nums[j]) continue;
                //z为组合需要的那个值
                int z = 0 - x - y;
                //如果map集合里面有这个值，最重要的是要判断它的value（序号）是不是在i和j的后面
                //因为之前的第三重for循环的k是从j + 1开始的，所以它一定会大于j
                if (map.containsKey(z) && map.get(z) > j) {
                    List<Integer> list = new LinkedList<Integer>();
                    list.add(x);
                    list.add(y);
                    list.add(z);
                    results.add(list);
                }
            }
        }
        return results;
    }

    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int x = nums[i];
            if (x > 0) {
                break;
            }
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[left] + x > 0) {
                    break;
                }
                if (nums[left] + nums[right] + x > 0) {
                    while (left < right && nums[right] == nums[--right]) {

                    }
                } else if (nums[left] + nums[right] + x < 0) {
                    while (left < right && nums[left] == nums[++left]) {

                    }
                } else {
                    results.add(Arrays.asList(nums[left], x, nums[right]));
                    while (left < right && nums[right] == nums[--right]) ;
                    while (left < right && nums[left] == nums[++left]) ;
                }
            }
        }
        return results;
    }

}
